#include<iostream>
#include<string>
#include<vector>
#include<stack>
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
using namespace std;

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Solution {
public:

    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st)
    {
        if (root == NULL)
            return false;
        st.push(root);
        if (root == x)
        {
            return true;
        }

        if (GetPath(root->left, x, st))
        {
            return true;
        }

        if (GetPath(root->right, x, st))
        {
            return true;
        }
        st.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        stack<TreeNode*>st1;
        stack<TreeNode*>st2;
        GetPath(root, p, st1);
        GetPath(root, q, st2);

        while (st1.top() != st2.top())
        {
            if (st1.size() > st2.size())
            {
                st1.pop();
            }

            else if (st1.size() < st2.size())
            {
                st2.pop();
            }
            else
            {
                st1.pop();
                st2.pop();
            }
        }
        return st1.top();
    }
};